package main

import (
	"fmt"
)

//#link: https://leetcode-cn.com/problems/next-permutation/
func main() {
	nums := []int{3, 2, 1}
	nextPermutation(nums)
	fmt.Println(nums)
}

//实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
func nextPermutation(nums []int) {
	//从最后以为开始比较
	numsLen := len(nums)
	if numsLen <= 1 {
		return
	}
	minNumIndex := 0
	//第一步，从后往前找，寻找第一个逆序的数
	for i := numsLen - 1; i >= 0; i-- {
		if i-1 > 0 && nums[i-1] < nums[i] {
			minNumIndex = i - 1
			break
		}
	}
	s := func() {
		left, right := minNumIndex+1, numsLen-1
		for left <= ((right + left) >> 1) {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}
	//从后往前寻找最大数的索引位置
	for i := numsLen - 1; i > minNumIndex; i-- {
		if nums[minNumIndex] < nums[i] {
			//交换最小数与最大数
			nums[minNumIndex], nums[i] = nums[i], nums[minNumIndex]
			//使最小数索引右边的数进行反转
			s()
			return
		}
	}
	minNumIndex = -1
	s()

	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
